1. Field of the Invention
The invention in general relates to computer-assisted circuit design and more particularly to apparatus and methods for optimization of the design of programmable logic device circuits.
2. Statement of the Problem
Programmable logic devices (PLDs) are integrated circuit chips having a group of PLD inputs and a group of PLD outputs connected by a logic circuit that can be programmed by fusing various connecting wires. The logic circuit typically comprises an AND array, a set of OR gates, and a set of registers. The PLD inputs are applied to the AND array, the outputs of the AND array are input to the OR gates, the outputs of the OR gates are input to the registers, and the register outputs provide the PLD outputs. An enable driver may be interposed between each register output and the corresponding PLD output. Many state-of-the art PLDs also have XOR gates and inverters connected between the OR gates and the registers, and the XOR gates and inverters may or may not have a fusible bypass. Sometimes the inverter may be placed between the register and the PLD output. Generally the fusible inverter is implemented as an XOR gate with one input grounded and a fuse between the input and ground. Some or all of the registers may also have outputs that feed back into the logic array. Generally, such registers can be used as inputs, should the lines normally referred to as PLD inputs not be sufficient to implement the design. Generally, any conductor connecting any internal logic device to another is referred to as a node. A symbol identifies anything that inputs into the array, which includes the PLD inputs, any PLD output that can feed back into the array, and any internal node that feeds back into the array. The outputs together with any internal node that can feed back into the array are referred to as "resources".
Early PLDs were programmed simply by the programmer understanding the circuits and fusing appropriate wires in the AND array to cause the PLD to function as desired. However, as PLDs increased in number of inputs and outputs and the complexity of the circuits, it became difficult to program a PLD correctly without wasteful trial and error. Moreover, there are many ways to program a PLD to arrive at any particular function, and generally manual methods do not lead to the most efficient result. It is well-known, however, that logic devices and their interrelationships can be described in terms of Boolean algebra. In particular the logic in PLDs can be described in a sum-of-products representation. A sum-of-products representation consists of a logical OR of product terms. A product term is a logical AND of symbols or negated symbols. The operators OR, AND, and NEGATE are conventional Boolean operators represented as "+", "*", and "/" respectively Generally the inputs and outputs are represented as symbols, and in the discussion herein the inputs will be represented as letters at the beginning of the alphabet, such as a, b, and c, and the PLD outputs will be represented as letters at the ending of the alphabet, such as x, y, or z. For example x=a*b+c is a Boolean algebra sum-of-products equation stating that the logic value of the PLD output node x is equal to the Boolean sum of the product a,b and the product "c", where a, b, and, c represent the logic values of the input nodes. Each of the product terms (pterms), such as a*b and c in the above equation, represent a wire input into one of the OR gates. Thus, when it became difficult or impossible to program PLDs effectively by manual methods, design tools were introduced allowing designs to be described using high level language representations, that is representations that more closely resemble the way in which humans think, which representations were then manipulated to implement the logic in a PLD. Typical PLD design programs are Abel.TM. produced by Data I/O, Inc. and CUPL.TM. produced by Logical Devices, Inc.
Generally, the designer inputs the design parameters into the system either by means of a high level hardware description language (HDL) or by using draw tool software to input a schematic which is translated by software into a representation that can be read by the design software. Constraints on the equations are also input, by making declarations in high level languages, designating specific devices or values for nodes in schematics, and by selecting system parameters. A compiler then constructs Boolean equations representing the input design parameters and constraints, which equations are then reduced to a minimal representation via conventional algorithms, such as Espresso, a well-known reduction software package. The design program translates the resulting equations into data files that can be read by automatic PLD programming devices to fuse the appropriate wires in the PLDs to implement the design.
More recently, programs have been created which not only can design and implement the logic in a single PLD, but can also partition the equations to implement the logic in multiple PLDs. See for example U.S. patent application Ser. No. 07/782,288 on an invention of William O. McDermith et al. and the PLDesigner.TM. 2.1 software produced by Minc, Incorporated. The above systems also have the ability to consider user specified preferences, such as cost, speed, power consumed, and space occupied by a system to select the optimum implementation for the user's needs.
A disadvantage of the above-described PLD computer-assisted design tools are that they require the user to target particular designs. That is, their compilers all use predefined mappings from the constructs used to describe the logic to the implementation of the description in equations. This restricts the form of the equations to those included in the predefined mappings, and the designs to those corresponding to the restricted equations. In particular, the prior art PLD design tools require the user to declare a node in order to insert a node into the equations and require a user to avoid declaring a node to avoid having one implemented. This leaves the designer responsible for finding optimum solutions, and thus also restricts the range of the implementations. Thus there is a need for a PLD computer-assisted design system which permits the user to design at a higher level and permits more flexibility in implementing the final design. In particular there is a need for a PLD design tool that provides a compiler that can adjust the mappings on the fly to a more general set of equations.
In recent years complex software programs have been developed to optimize generalized logical structure. See for example, MIS: A Multiple-Level Logic Optimization System, by Robert K. Brayton, Richard Rudell, Alberto Sangiovanni-Vincentelli, and Albert R. Wang, IEEE Transactions On Computer Aided Design, Vol. CAD-6 No. 6, November 1987, pp. 1062-1082. Likewise, programs have been developed to optimize generalized logic circuits. See for example, The Olympus Synthesis System: by De Micheli, Ku, Mailhot, and Truong, IEEE Design and Test of Computers, October 1990, pp. 37-53. The above-referenced paper by Brayton et al. describes an optimization system in which the step of optimizing the Boolean equations comprises minimizing the area occupied by the logic equations, which, in terms of the electrical components, means that the electronic elements used are minimized. While this approach is efficient in terms of logic structure, it often does not result in the most effective use of PLDs. Minimizing the area of the equations can result in more equations, though each equation is short. Since, a PLD has a fixed number of resources and a fixed set of logic components, the optimal use of the logic according to the MIS paper may use up all the resources while leaving some of the logic components unused. This can result in an inefficient use of the PLDs because more PLDs than are necessary may be required to implement a design optimized in terms of total logic components. Thus there is a need for an optimization system that optimizes the use of PLDs in general, and in particular optimizes the number of resources used, within the constraints of the logic elements available.
In PLD logic circuits, as in all logic circuits, there are certain conditions in which particular nodes are designed to be in a logic 1 or ON state, other conditions in which the same nodes are designed to be in a logic 0 or OFF state, and other conditions in which the state of the same nodes is irrelevant, which conditions are called "DONT CARE" conditions. While the DONT CARE conditions are immaterial to the logic system operation, the DONT CARE information, that is the specifications of the various conditions for which the value of a symbol is irrelevant, is often useful in programming PLDs because a design that may not be implementable if a condition was specified as ON or OFF may be implementable if the condition is a "DONT CARE" condition, because the reduced equation may be smaller. Thus, prior art optimization systems, such as the system described in the Brayton et al. reference, provide for the specification of DONT CARE information by permitting the designer to declare certain conditions as DONT CARE conditions. Thus there is a need for an optimization system that preserves all DONT CARE information so that it can be taken advantage of during the hardware implementation.
As indicated above, many PLDs contain a set of registers. These registers may be implemented as either a D flip-flop, a JK flip-flop, an SR flip-flop, or a T flip-flop. Generally, a user may write the input equations in terms of one flip-flop, or the schematic is implemented in a specific flip-flop. This will tend to limit the device fitting process from the start, since the devices available to implement the described design depend on the flip-flop type used in the description. Thus an optimization system that is able to optimize for any flip-flop implementation would be highly desirable.
Prior art PLD tools may not be able to handle arithmetic operations for operands having more than a small number of bits. This is because the equations for such operations increase exponentially with the number of bits. By the time there are five or more bits, the equations may be so large that they no longer can be handled by the prior art systems, and even when they can be handled, the equations may be quite large, restricting the set of devices able to implement the design. Since operators having widths of eight bits and larger are becoming commonplace in digital circuitry, there is a need for a PLD design system that can handle arithmetic operands of arbitrary width.
3. Solution to the problem
The present invention solves the above problems by providing a computerized logic design system having an optimizer that minimizes the number of nodes used in the equations without exceeding the capabilities of the target devices. This means the number of resources used by the system is minimized.
The above minimization is performed with the constraint that the number of symbols in any given equation is less than or equal to a predetermined number set by the user. Since the symbols represent inputs, outputs that are used as inputs, and nodes that feed back into the array, and since the number of inputs is limited, this ensures that logic implementation will not exceed the resources available in the target hardware.
The above minimization is performed with the additional constraint that the number of product terms (pterms) in the sum of product equations is less than or equal to a predetermined number set by the user. Since the pterms represent the OR inputs, this ensures that sufficient OR inputs will be available to implement the design.
The optimizer according to the invention also utilizes user selectable parameters that take into account whether fusible inverters are present, whether the logic includes exclusive OR gates, and whether the target hardware has a fusible inverter to control the polarity of the exclusive OR. In each case the capabilities of the device is taken into account in the optimization of the equations, and all equations are retained that enhance the selections available.
The minimization of the nodes is accomplished by tentatively collapsing nodes into the other equations, checking to see if any of the other equations expand beyond the limits discussed above, and then collapsing only if the collapsed equations would be acceptable in terms of the above criteria.
In order to increase the flexibility of choosing which nodes to collapse, prior to node collapsing, nodes are introduced at the carry-bits of arithmetic and relational operators, at function and procedure boundaries, and at the condition equation of complex IF statements. This introduction of nodes, allows the optimizer according to the invention to handle operators of arbitrary bit widths. It also results in a more generalized group of starting equations and more flexibility in creating nodes, optimization, and implementing the logic system.
The computerized logic design system according to the invention also provides a compiler that for each of each of the Boolean equations in the representation, writes both the ON version of the equation and the OFF version of the equation. The optimization process is performed separately for both equations, thus both equations are retained throughout the optimization process. Since the DONT CARE information consists of every condition not included in either the ON equation or the OFF equation, all DONT CARE information is retained throughout the optimization process.
The optimizer according to the invention also synthesizes all register implementations, utilizing all the possible flip-flop types. The synthesis is performed by translating each equation that feeds a flip-flop into the corresponding equations for an identical circuit having all the other varieties of flip-flops substituted for the specified flip-flop. For example, if equations are described feeding the J and K inputs of a JK flip-flop, the equations are translated into equations that feed the D input of a D flip-flop, the S and R inputs of an SR flip-flop, and the T input of a T flip-flop. Equation reduction is performed on each of these representations so that each representation is minimal. The automatic partitioning system as described in the McDermith et al. application referenced above can then implement the associated symbol in devices with any flip-flop type.
The register synthesis is performed by mapping each equation for a flip-flop that is not a D flip-flop into the equation for a D flip-flop and then from the D flip-flop to every other type of flip-flop. This process optimizes the two equations for the JK flip-flop, and the two equations for the SR flip flop, since it incorporates the interactions of the equations into the optimization system.